/*************************************************************************
 * File Name:    Clone_Graph.cc
 * Author:       zero91
 * Mail:         jianzhang9102@gmail.com
 * Created Time: Wed 30 Oct 2013 11:13:14 PM CST
 * 
 * Description:  
 |-------------------------------------------------------------------------
 | Problem: Clone Graph
 | Clone an undirected graph. Each node in the graph contains a label and a
 | list of its neighbors.
 |
 | OJ's undirected graph serialization:
 | Nodes are labeled uniquely.
 |
 | We use # as a separator for each node, and , as a separator for node label 
 | and each neighbor of the node.
 |
 | As an example, consider the serialized graph {0,1,2#1,2#2,2}.
 |
 | The graph has a total of three nodes, and therefore contains three parts
 | as separated by #.
 |
 | First node is labeled as 0. Connect node 0 to both nodes 1 and 2.
 | Second node is labeled as 1. Connect node 1 to node 2.
 | Third node is labeled as 2. Connect node 2 to node 2 (itself),
 | thus forming a self-cycle.
 |
 | Visually, the graph looks like the following:
 |
 |        1
 |       / \
 |      /   \
 |     0 --- 2
 |          / \
 |          \_/
 |------------------------------------------------------------------------
 ************************************************************************/

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <deque>
#include <map>
#include <set>
#include <functional>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cmath>
#include <iomanip>

using namespace std;

/**
 * Definition for undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
class Solution {
private:
    typedef pair<UndirectedGraphNode *, UndirectedGraphNode *> GraphNodePair;

public:
    UndirectedGraphNode *cloneGraph(UndirectedGraphNode *node) {
        if (node == NULL) return NULL;
        
        map<UndirectedGraphNode *, UndirectedGraphNode *> m;
        
        UndirectedGraphNode *ans = new UndirectedGraphNode(node->label);
        queue<GraphNodePair> Q;
        GraphNodePair t;
        
        m[node] = ans;
        Q.push(make_pair(node, ans));
        while (!Q.empty()) {
            t = Q.front(), Q.pop();
            for (size_t i = 0; i < t.first->neighbors.size(); ++i) {
                if (m.find(t.first->neighbors[i]) != m.end()) {
                    t.second->neighbors.push_back(m[t.first->neighbors[i]]);
                } else {
                    t.second->neighbors.push_back(new UndirectedGraphNode(t.first->neighbors[i]->label));
                    m[t.first->neighbors[i]] = t.second->neighbors[i];
                    Q.push(make_pair(t.first->neighbors[i], t.second->neighbors[i]));
                }
            }
        }
        return ans;
    }
};
